package application;

import zhengqc.list.ArrayList;
import zhengqc.list.LinkedList;
import zhengqc.list.List;
import zhengqc.queue.LoopQueue;
import zhengqc.queue.Queue;

import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;

public class BinaryTree {
    public static enum BinaryTreeRebuildType {
        PRE_IN,
        POST_IN,
    }
    public static enum BinaryTreeSerializeType {
        PREORDER,
        INORDER,
        POSTORDER,
    }
    class Node {
        public Node left;
        public Character element;
        public Node right;
        public Node(Node left, Character element, Node right) {
            this.left = left;
            this.element = element;
            this.right = right;
        }
        public Node(Character element) {
            this(null, element, null);
        }
    }
    protected List<Character> tempList;
    private Node root;
    private Character Separator;
    private Character NULL;

    public BinaryTree() {
        this(',', '#');
    }
    public BinaryTree(Character Separator, Character NULL) {
        this.tempList = new ArrayList<>();
        this.root = null;
        this.Separator = Separator;
        this.NULL = NULL;
    }
    /* 先序遍历 */
    protected void preorder(Node node) {
        if (node == null) {
            return;
        }
        this.tempList.addLast(node.element);
        preorder(node.left);
        preorder(node.right);
    }
    /* 中序遍历 */
    protected void inorder(Node node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        this.tempList.addLast(node.element);
        inorder(node.right);
    }
    /* 后序遍历 */
    protected void postorder(Node node) {
        if (node == null) {
            return;
        }
        postorder(node.left);
        postorder(node.right);
        this.tempList.addLast(node.element);
    }
    /* 层序遍历 */
    protected void level(Node node) {
        Queue<Node> queue = new LoopQueue<>();
        queue.enqueue(node);
        while (!queue.isEmpty()) {
            Node current = queue.dequeue();
            this.tempList.addLast(current.element);
            if (current.left != null) {
                queue.enqueue(current.left);
            }
            if (current.right != null) {
                queue.enqueue(current.right);
            }
        }
    }
    /* 遍历二叉树 */
    public List<Character> traversal(String method) {
        this.tempList.clear();
        switch (method) {
            case "preorder":
                preorder(this.root);
                break;
            case "inorder":
                inorder(this.root);
                break;
            case "postorder":
                postorder(this.root);
                break;
            case "level":
                level(this.root);
        }
        return this.tempList;
    }

    /* 重新构造二叉树 */
    public void rebuild(Character[] order1, Character[] order2, BinaryTreeRebuildType rebuild_type) {
        Map<Character, Integer> map = new TreeMap<>();
        Character[] inorder = order2;
        for (int i = 0; i < inorder.length; ++i) {
            map.put(inorder[i], i);
        }
        switch (rebuild_type) {
            case PRE_IN:
                Character[] preorder = order1;
                this.root = this.__rebuild_pre_in__(0, 0, inorder.length-1, preorder, inorder, map);
                break;
            case POST_IN:
                Character[] postorder = order1;
                this.root = this.__rebuild_post_in__(postorder.length-1, 0, inorder.length-1, postorder, inorder, map);
                break;
        }
    }
    /* 根据前序遍历和中序遍历重新构造二叉树 */
    private Node __rebuild_pre_in__(
            int pre_left, int in_left, int in_right,
            Character[] preorder, Character[] inorder, Map<Character, Integer> map) {
        if (in_left > in_right) return null;
        Node node = new Node(preorder[pre_left]);
        int index = map.get(preorder[pre_left]);
        node.left = this.__rebuild_pre_in__(
                pre_left+1, in_left, index-1,
                preorder, inorder, map);
        node.right = this.__rebuild_pre_in__(
                pre_left+(index-in_left)+1, index+1, in_right,
                preorder, inorder, map);
        return node;
    }
    /* 根据后序遍历和中序遍历重新构造二叉树 */
    private Node __rebuild_post_in__(
            int post_right, int in_left, int in_right,
            Character[] postorder, Character[] inorder, Map<Character, Integer> map) {
        if (in_left > in_right) return null;
        Node node = new Node(postorder[post_right]);
        int index = map.get(postorder[post_right]);
        node.left = this.__rebuild_post_in__(
                post_right-in_right+index-1, in_left, index-1,
                postorder, inorder, map);
        node.right = this.__rebuild_post_in__(
                post_right-1, index+1, in_right,
                postorder, inorder, map);
        return node;
    }

    /* 序列化二叉树 */
    public String serialize(BinaryTreeSerializeType serialize_type) {
        StringBuilder sb = new StringBuilder();
        switch (serialize_type) {
            case PREORDER:
                this.__serialize_pre__(this.root, sb);
                break;
            case INORDER:
                this.__serialize_in__(this.root, sb);
                break;
            case POSTORDER:
                this.__serialize_post__(this.root, sb);
                break;
        }
        if ( this.Separator.equals(sb.charAt(sb.length()-1)) ) {
            sb.delete(sb.length()-1, sb.length());
        }
        return sb.toString();
    }
    /* 使用前序遍历方法序列化二叉树 */
    private void __serialize_pre__(Node root, StringBuilder sb) {
        if (root == null) {
            sb.append(this.NULL).append(this.Separator);
            return;
        }
        sb.append(root.element).append(this.Separator);
        this.__serialize_pre__(root.left, sb);
        this.__serialize_pre__(root.right, sb);
    }
    /* 使用中序遍历方法序列化二叉树 */
    private void __serialize_in__(Node root, StringBuilder sb) {
        if (root == null) {
            sb.append(this.NULL).append(this.Separator);
            return;
        }
        this.__serialize_in__(root.left, sb);
        sb.append(root.element).append(this.Separator);
        this.__serialize_in__(root.right, sb);
    }
    /* 使用后序遍历方法序列化二叉树 */
    private void __serialize_post__(Node root, StringBuilder sb) {
        if (root == null) {
            sb.append(this.NULL).append(this.Separator);
            return;
        }
        this.__serialize_post__(root.left, sb);
        this.__serialize_post__(root.right, sb);
        sb.append(root.element).append(this.Separator);
    }

    /* 反序列化二叉树 */
    public void deserialize(Character[] sequence, BinaryTreeSerializeType serialize_type) {
        LinkedList<Character> nodes = new LinkedList<>();
        for (Character c: sequence) {
            if (c.equals(this.Separator)) continue;
            nodes.addLast(c);
        }
        switch (serialize_type) {
            case PREORDER:
                this.root = this.__deserialize_pre__(nodes);
                break;
            case POSTORDER:
                this.root = this.__deserialize_post__(nodes);
                break;
            default:
                System.out.println("未能反序列化!");
        }

    }
    /* 根据前序遍历方法反序列化二叉树 */
    private Node __deserialize_pre__(LinkedList nodes) {
        if (nodes.isEmpty()) return null;
        Character first = (Character) nodes.removeFirst();
        if (first.equals(this.NULL)) return null;
        Node root = new Node(first);
        root.left = this.__deserialize_pre__(nodes);
        root.right = this.__deserialize_pre__(nodes);
        return root;
    }
    /* 根据后序遍历方法反序列化二叉树 */
    private Node __deserialize_post__(LinkedList nodes) {
        if (nodes.isEmpty()) return null;
        Character last = (Character) nodes.removeLast();
        if (last.equals(this.NULL)) return null;
        Node root = new Node(last);
        root.right = this.__deserialize_post__(nodes);
        root.left = this.__deserialize_post__(nodes);
        return root;
    }

    /* 获取二叉树的深度 */
    public int getDepth() {
        return this.getDepth(this.root);
    }
    /* 获取以 node 为根的二叉树的深度 */
    private int getDepth(Node node) {
        if (node == null) return 0;
        return Math.max(getDepth(node.left), getDepth(node.right)) + 1;
    }

    /* 统计叶子节点个数 */
    public int countLeafNode() {
        return this.countLeafNode(this.root);
    }
    /* 统计以 node 为根的叶子节点个数 */
    private int countLeafNode(Node node) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return 1;
        return this.countLeafNode(node.left) + this.countLeafNode(node.right);
    }

    /* 统计节点个数 */
    public int countNode() {
        return this.countNode(this.root);
    }
    /* 统计以 node 为根的节点个数 */
    private int countNode(Node node) {
        if (node == null) return 0;
//        System.out.println(node.element + " " + "left:" + countLeafNode(node.left) + " right:" + countLeafNode(node.right));
        return this.countNode(node.left) + this.countNode(node.right) + 1;
    }
}
